package leetcode.editor.cn;
 
/**
 * 最后一块石头的重量 II
 * @author qulq
 * @date 2024-07-10 22:07:16
 */
public class T1049_LastStoneWeightIi{
	 public static void main(String[] args) {
	 	 //测试代码
	 	 Solution solution = new T1049_LastStoneWeightIi().new Solution();
	 }

	/**
	 * 本题其实就是尽量让石头分成重量相同的两堆，相撞之后剩下的石头最小，这样就化解成01背包问题了。
	 */
//力扣代码
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public int lastStoneWeightII(int[] stones) {
		int sum = 0;
		for (int stone : stones) {
			sum += stone;
		}
		// 向下取整，剩下一半 sum - dp[target] 一定是大于等于dp[target]的
		int target = sum / 2;
		int[] dp = new int[target + 1];
		for (int i = 0; i < stones.length; i++) {
			for (int j = target; j >= stones[i]; j--) {
				dp[j] = Math.max(dp[j], dp[j - stones[i]] + stones[i]);
			}
		}
		return sum - dp[target] - dp[target];
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}